package leetcode.editor.cn;

//给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。 
//
// 你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。 
//
// 
//
// 示例 1： 
//
// 
//输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
//输出：[[7,4,1],[8,5,2],[9,6,3]]
// 
//
// 示例 2： 
//
// 
//输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
//输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
// 
//
// 示例 3： 
//
// 
//输入：matrix = [[1]]
//输出：[[1]]
// 
//
// 示例 4： 
//
// 
//输入：matrix = [[1,2],[3,4]]
//输出：[[3,1],[4,2]]
// 
//
// 
//
// 提示： 
//
// 
// matrix.length == n 
// matrix[i].length == n 
// 1 <= n <= 20 
// -1000 <= matrix[i][j] <= 1000 
// 
// Related Topics 数组 数学 矩阵 👍 1059 👎 0

import java.util.Arrays;

//Java：旋转图像
public class RotateImage_48{
    public static void main(String[] args) {
        Solution solution = new RotateImage_48().new Solution();
        // TO TEST
        //   [a][b]    ---   [b][n-a-1]
        //      |                 |
        //      |                 |
        // [n-b-1][a]  ---  [n-a-1][n-b-1]
        //
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n/2; i++) { // 共有n/2个圈
            for (int j = 0; j < n-2*i-1; j++) { // 每个圈拆分为四个等长线段
                swap(matrix, i, i+j, i+j, n-1-i);
                swap(matrix, i, i+j, n-1-i, n-1-i-j);
                swap(matrix, i, i+j, n-1-i-j, i);
            }

        }
    }
    public void swap(int[][] matrix, int a, int b,int c,int d){
        int tmp = matrix[c][d];
        matrix[c][d] = matrix[a][b];
        matrix[a][b] = tmp;
    }
}
//leetcode submit region end(Prohibit modification and deletion)


    public void rotate(int[][] matrix) {
        int n=matrix.length,round = 0;
        while (round<n/2) {
            int a=round,b=round;
            for (int i = 0; i < n-2*round-1; i++) {
                int pre = matrix[a][b];
                for (int j = 0; j < 4; j++) {
                    int tmp = matrix[b][n-a-1];
                    matrix[b][n-a-1] = pre;
                    pre = tmp;
                    int c=a;
                    a=b;
                    b=n-c-1;
                }
                b++;
            }
            round++;
        }
    }
}
